TNotes.leetcode

Appearance

0997. 找到小镇的法官【简单】

0997. 找到小镇的法官【简单】 ​

1. 📝 题目描述 ​

小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。

如果小镇法官真的存在，那么：

  1. 小镇法官不会信任任何人。
  2. 每个人（除了小镇法官）都信任这位小镇法官。
  3. 只有一个人同时满足属性 1 和属性 2。（注：这句话相当于在说小镇法官只有一个人）

给你一个数组 trust，其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。

如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 -1。

示例 1：

txt
输入：n = 2, trust = [[1,2]]
输出：2

示例 2：

txt
输入：n = 3, trust = [[1,3],[2,3]]
输出：3

示例 3：

txt
输入：n = 3, trust = [[1,3],[2,3],[3,1]]
输出：-1

提示：

  • 1 <= n <= 1000
  • 0 <= trust.length <= 10^4
  • trust[i].length == 2
  • trust 中的所有 trust[i] = [ai, bi] 互不相同
  • ai != bi
  • 1 <= ai, bi <= n

2. 🎯 s.1 - 暴力解法 ​

js
/**
 * @param {number} n
 * @param {number[][]} trust
 * @return {number}
 */
var findJudge = function (n, trust) {
  // 统计每个人被相信的次数和相信的次数
  const trustCount = new Array(n + 1).fill(0)
  const distrustCount = new Array(n + 1).fill(0)

  for (let [a, b] of trust) {
    distrustCount[a]++ // a 相信了一个人
    trustCount[b]++ // b 被相信了一次
  }

  // 法官是被所有其他 n-1 个人都相信的人，且自己不相信任何人
  for (let i = 1; i <= n; i++) {
    if (trustCount[i] === n - 1 && distrustCount[i] === 0) {
      return i
    }
  }

  // 如果没有法官，返回 -1
  return -1
}
  • 时间复杂度：O(n⋅m)，对每个候选人扫描一次 trust，其中 n 为人数、m 为 trust.length
  • 空间复杂度：O(1)，仅使用常数额外变量

算法思路：

  • 枚举每个人 p，分别检查两条性质：
    • 不信任任何人：trust 中不存在形如 [p, x] 的记录
    • 被所有其他人信任：统计 trust 中以 p 为终点的记录数是否为 n−1
  • 若存在同时满足两条性质的人则返回其编号，否则返回 -1

3. 🎯 s.2 - 净信任度（入度-出度） ​

js
/**
 * @param {number} n
 * @param {number[][]} trust
 * @return {number}
 */
var findJudge = function (n, trust) {
  const score = new Array(n + 1).fill(0)
  for (const [a, b] of trust) {
    score[a]--
    score[b]++
  }
  for (let i = 1; i <= n; i++) {
    if (score[i] === n - 1) return i
  }
  return -1
}
  • 时间复杂度：O(n+m)，其中 n 为人数、m 为 trust.length
  • 空间复杂度：O(n)

算法思路：

  • 用净信任度数组记录每人被信任次数减去其信任他人次数：对 a 记 -1，对 b 记 +1
  • 法官满足净信任度为 n−1（被所有其他人信任且不信任任何人），线性扫描即可找到

Discussions